import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree{

    private static BTNode root;

    public static class BTNode {
                BTNode left;
                BTNode right;
                char val;

                public BTNode(char val) {
                    this.val = val;
                }

            }

    public static BTNode createBinaryTree(){
        BTNode node1 = new BTNode((char) 1);
        BTNode node2 = new BTNode((char) 2);
        BTNode node3 = new BTNode((char) 3);
        BTNode node4 = new BTNode((char) 4);
        BTNode node5 = new BTNode((char) 5);
        BTNode node6 = new BTNode((char) 6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
        return root;
        }
//public BTNode createTree(int index) { // 采用递归生成二叉树
//    if (index >= size)
//        return null;
//    if (val[index] == '0')
//        return null;
//    BTNode node = new BTNode(val[index]);
//    node.setLeft(createTree(2 * index + 1));
//    node.setRight(createTree(2 * index + 2));
//    return node;
//}
//
//public BTNode getRoot(BTNode root){
//        return root;
//}

//前序遍历
    public static void  preOrder(BTNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
}
//中序遍历
    public static void inOrder(BTNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
}
//后序遍历
    public  void  postOrder(BTNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

//获取树中结点个数
    public int NodeNum(BTNode root){
    if(root==null){
        return 0;
    }
    int leftSize=NodeNum(root.left);
    int rightSize=NodeNum(root.right);
    return leftSize+rightSize+1;
}

    // 获取叶子节点的个数
    int getLeafNodeCount(BTNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        int leftSize=getLeafNodeCount(root.left);
        int rightSize=getLeafNodeCount(root.right);
        return  leftSize+rightSize;
    }

// 获取第K层节点的个数
    public int getKLevelNodeCount(BTNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        int leftSize=getKLevelNodeCount(root.left,k-1);
        int rightSize=getKLevelNodeCount(root.right,k-1);
        return  leftSize+rightSize;
    }
    // 获取二叉树的高度
    int getHeight(BTNode root){
        if(root==null){
            return 0;
        }
        int leftHigh=getHeight(root.left);
        int rightHigh=getHeight(root.right);
        return (leftHigh>rightHigh)?(leftHigh+1):(rightHigh+1);
    }
    // 检测值为value的元素是否存在
    public  BTNode find(BTNode root, int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        BTNode ret=find(root.left,val);
        if(ret!=null){
            return ret;
        }
        return find(root.right,val);
    }
    //层序遍历
    public  void levelOrder(BTNode root){
        if(root==null){
            return;
        }
       Queue<BTNode> queue= new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BTNode cur=queue.poll();
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
    //层序遍历第二种方法：返回值为list类型
    public static List<List<Character>> levelOrder1(BTNode root){
        List<List<Character>> ret=new LinkedList<>();  //ret是大的list
        if(root==null){return ret;}
        Queue<BTNode> queue=new LinkedList<>();
        queue.offer(root);//将根结点入队列
        while(!queue.isEmpty()){
            // 1.求当前队列的大小,size
            int size=queue.size();//求队列当前的大小
            List<Character> list=new ArrayList<>();
            // 2.while(size>0)  ---->控制当前每一层的数据个数
            while(size>0) {
                BTNode cur = queue.poll();//当队列里有元素时，就将该队列的首元素出队列
                if(cur!=null){  //当cur的值不为空时
                    list.add(cur.val);//就将cur里的元素放进list里
                    if(cur.left!=null){
                        queue.offer(cur.left);//将cur.left入队列
                    }
                    if(cur.right!=null){
                        queue.offer(cur.right);
                    }
                }
                size--;//刚刚队列里面有一个元素，现在--后就没有了，所以跳出这层循环
            }
            ret.add(list);//将list里的元素放进大的list中
        }
        return ret;//最终队列为空时，循环终止，返回大list，若是代码看不懂就将代码仔细的口头运行一遍，会懂的！
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(BTNode root){
        if(root==null){
            return true;
        }
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            BTNode cur= queue.peek();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while (!queue.isEmpty()){
            BTNode tmp = queue.poll();
            if(tmp!=null){
                return false;
            }
        }
        return true;
    }




}